# function

import sys
import functools


# Classic functional programming high-level functions

# map

if sys.version_info.major == 3:
    reduce = functools.reduce

filter = lambda f, coll: [x for x in coll if f(x)] if f else [x for x in coll if x]

def group_by(f, coll):
    d = {}
    for it in coll:
        k = f(it)
        d[k] = d.get(k, []) + [it]
    return d

def compose(obj, *fns):
    """Compose functions into sequence."""
    for f in fns:
        obj = f(obj)
    return obj


def typecheck(func):
    def do_check(name, arg):
        etype = func.__annotations__.get(name, None) # expected type
        if etype and not isinstance(arg, etype):
            raise RuntimeError("%s should be of type %s, but %s got"
                               % (name, etype.__name__, type(arg).__name__))
    @functools.wraps(func)
    def wrapper(*args, **kw):
        for i, arg in enumerate(args[:func.__code__.co_nlocals]):
            do_check(func.__code__.co_varnames[i], arg)
        for name, arg in kw.items():
            do_check(name, arg)
        result = func(*args, **kw)
        do_check('return', result)
        return result
    return wrapper



class TailRecurseException: pass

def tail_call_optimized(g):
    '''This function decorates a function with tail call
    optimization. It does this by throwing an exception if
    it is it's own grandparent, and catching such exceptions
    to fake the tail call optimization. It fails if the
     decorated function recurses in a non-tail context.'''
    def func(*args, **kwargs):
        f = sys._getframe()
        if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
            raise TailRecurseException(args, kwargs)
        else:
            while 1:
                try:
                    return g(*args, **kwargs)
                except TailRecurseException as e:
                    args = e.args
                    kwargs = e.kwargs
        func.__doc__ = g.__doc__
        return func
